package com.test.suanfa;

/**
 * 输入一个X值，找到最接近x的平方根  比如25开根号=5
 * 使用方式：二分查找
 */
public class 二分查找 {

    public static void main(String[] args) {
        System.out.println(search(25));
        System.out.println(search2(25));
    }

    public static int search2(int x) {
        int index = -1, l = 0, r = x;
        for (int i = 0; i < x; i++) {
            int mid = l + (r - l);
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                l = l + 1;
            } else {
                r = r - 1;
            }
        }
        return index;
    }


    public static int search1(int x) {
        int index = -1, l = 0, r = x;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                l = l + 1;
            } else {
                r = r - 1;
            }
        }
        return -1;
    }


    public static int search(int x) {
        // 定义返回值index，左指针从0开始，右指针从x最大值开始，中间指针0
        int index = -1, l = 0, r = x, mid = 0;
        // 定义循环结束条件
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (mid * mid <= x) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }
}
